package cn.bellychang.leetcode.question088;

/**
 * @author ChangLiang
 * @date 2021/2/9
 */
public class Solution2 {

    /**
     * 时间复杂度是O(n * 1)
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int insertionIndex = -1;

        for (int num : nums2) {
            insertionIndex = getInsertionIndex(nums1, num, m, insertionIndex + 1);
            if (insertionIndex < m) {
                System.arraycopy(nums1, insertionIndex, nums1, insertionIndex + 1, (m - insertionIndex));
            }
            nums1[insertionIndex] = num;
            m++;
        }
    }

    private int getInsertionIndex(int[] nums1, int num, int m, int startIndex) {

        for (int i = startIndex; i < m; i++) {
            if (nums1[i] > num) {
                return i;
            }
        }
        return m;
    }
}
